package com.sunny.leetcode.链表;

/**
 * 反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。
 *
 * 说明:
 * 1 ≤ m ≤ n ≤ 链表长度。
 *
 * 示例:
 *
 * 输入: 1->2->3->4->5->NULL, m = 2, n = 4
 * 输出: 1->4->3->2->5->NULL
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/reverse-linked-list-ii
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 * @author Sunny
 * @date 2020/9/12
 */
public class _92_反转链表II {

    public static ListNode reverseBetween(ListNode head, int m, int n) {
        if (head == null || m > n) {
            return null;
        }

        //1. 指定一个虚拟节点
        ListNode dummyNode = new ListNode(-1);
        dummyNode.next = head;
        head = dummyNode;

        //2. 遍历至m的前一个节点
        for (int i = 1; i < m; i++) {
            head = head.next;
        }

        //head.next就是需要反转的这段的起点。
        ListNode nextHead = head.next;
        ListNode next = null;
        ListNode pre = null;
        for (int i = m; i <= n; i++) {
            //next = 3
            next = nextHead.next;
            //3 = null
            nextHead.next = pre;
            //pre = 2
            pre = nextHead;
            // 2 = 3
            nextHead = next;
        }
        //将反转的起点的next指向next。
        head.next.next = next;
        //需要反转的那一段的上一个节点的next节点指向反转后链表的头结点
        head.next = pre;
        return dummyNode.next;
    }
}
